Improving search for job-shop scheduling with CLP(FD)
Identifieur interne : 00CD18 ( Main/Exploration ); précédent : 00CD17; suivant : 00CD19Improving search for job-shop scheduling with CLP(FD)
Auteurs : Silvia Breitinger [Allemagne] ; Hendrik C. R. Lock [France]Source :
- Lecture Notes in Computer Science [ 0302-9743 ]
Abstract
Abstract: Constraint logic programming can be effectively applied to solve realistic job-shop scheduling problems. The role of constraints is twofold: they model dependencies among tasks and resources (e.g. temporal relations and capacities of machines), and they are used to actively prune the search space during the computation of a schedule. Since the job-shop problem is N P-complete, constraint solving techniques alone do not suffice to get efficient schedules for problems with 100 tasks and more. In order to judge a scheduling method, one has to investigate two questions: how good are the solutions in comparison to the optimum and how much search is required to find them. This paper reports on achievable improvements with respect to both aspects by applying three methods: an efficient encoding of capacity constraints, a new semi-dynamic variable selection heuristics, and an algorithm for enforcing global capacity constraints. The first method transfers choices inside capacity constraints entirely to the disposition of the solver, which optimally supports the available pruning capabilities. The second method orders variables in a way that prefers tasks that must be placed early or that occur in predicted machine bottlenecks. The third method detects inconsistencies at a early stage of search and is also able to enforce partial orderings among tasks. Tests on randomly generated problems have shown that the combination of these methods yields an average approximation of the optimum of 7–13% within a few hundred search steps, whereas without them the approximation had been worse than 120%.
Url:
DOI: 10.1007/3-540-58402-1_20
Affiliations:
- Allemagne, France
- District de Giessen, Grand Est, Hesse (Land), Lorraine (région)
- Marbourg, Vandœuvre-lès-Nancy
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 000B17
- to stream Istex, to step Curation: 000B11
- to stream Istex, to step Checkpoint: 002D07
- to stream Main, to step Merge: 00D586
- to stream Main, to step Curation: 00CD18
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Improving search for job-shop scheduling with CLP(FD)</title><author><name sortKey="Breitinger, Silvia" sort="Breitinger, Silvia" uniqKey="Breitinger S" first="Silvia" last="Breitinger">Silvia Breitinger</name></author><author><name sortKey="Lock, Hendrik C R" sort="Lock, Hendrik C R" uniqKey="Lock H" first="Hendrik C. R." last="Lock">Hendrik C. R. Lock</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:2FD619EC268C08B11C68A39EDE07A7ACA7E3F46F</idno><date when="1994" year="1994">1994</date><idno type="doi">10.1007/3-540-58402-1_20</idno><idno type="url">https://api.istex.fr/ark:/67375/HCB-RXNLSSNZ-S/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">000B17</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000B17</idno><idno type="wicri:Area/Istex/Curation">000B11</idno><idno type="wicri:Area/Istex/Checkpoint">002D07</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">002D07</idno><idno type="wicri:doubleKey">0302-9743:1994:Breitinger S:improving:search:for</idno><idno type="wicri:Area/Main/Merge">00D586</idno><idno type="wicri:Area/Main/Curation">00CD18</idno><idno type="wicri:Area/Main/Exploration">00CD18</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Improving search for job-shop scheduling with CLP(FD)</title><author><name sortKey="Breitinger, Silvia" sort="Breitinger, Silvia" uniqKey="Breitinger S" first="Silvia" last="Breitinger">Silvia Breitinger</name><affiliation wicri:level="3"><country xml:lang="fr">Allemagne</country><wicri:regionArea>Fachbereich Mathematik, Fachgebiet Informatik, Philipps-Universität Marburg, Hans-Meerwein-Straße, D-35032, Marburg</wicri:regionArea><placeName><region type="land" nuts="1">Hesse (Land)</region><region type="district" nuts="2">District de Giessen</region><settlement type="city">Marbourg</settlement></placeName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country></affiliation></author><author><name sortKey="Lock, Hendrik C R" sort="Lock, Hendrik C R" uniqKey="Lock H" first="Hendrik C. R." last="Lock">Hendrik C. R. Lock</name><affiliation wicri:level="3"><country xml:lang="fr">France</country><wicri:regionArea>CRIN & INRIA-Lorraine, BP 239, F-54506, Vandoeuvre-les-Nancy Cedex</wicri:regionArea><placeName><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region><settlement type="city">Vandœuvre-lès-Nancy</settlement></placeName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">France</country></affiliation></author></analytic><monogr></monogr><series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title><title level="s" type="abbrev">Lect Notes Comput Sci</title><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: Constraint logic programming can be effectively applied to solve realistic job-shop scheduling problems. The role of constraints is twofold: they model dependencies among tasks and resources (e.g. temporal relations and capacities of machines), and they are used to actively prune the search space during the computation of a schedule. Since the job-shop problem is N P-complete, constraint solving techniques alone do not suffice to get efficient schedules for problems with 100 tasks and more. In order to judge a scheduling method, one has to investigate two questions: how good are the solutions in comparison to the optimum and how much search is required to find them. This paper reports on achievable improvements with respect to both aspects by applying three methods: an efficient encoding of capacity constraints, a new semi-dynamic variable selection heuristics, and an algorithm for enforcing global capacity constraints. The first method transfers choices inside capacity constraints entirely to the disposition of the solver, which optimally supports the available pruning capabilities. The second method orders variables in a way that prefers tasks that must be placed early or that occur in predicted machine bottlenecks. The third method detects inconsistencies at a early stage of search and is also able to enforce partial orderings among tasks. Tests on randomly generated problems have shown that the combination of these methods yields an average approximation of the optimum of 7–13% within a few hundred search steps, whereas without them the approximation had been worse than 120%.</div></front></TEI><affiliations><list><country><li>Allemagne</li><li>France</li></country><region><li>District de Giessen</li><li>Grand Est</li><li>Hesse (Land)</li><li>Lorraine (région)</li></region><settlement><li>Marbourg</li><li>Vandœuvre-lès-Nancy</li></settlement></list><tree><country name="Allemagne"><region name="Hesse (Land)"><name sortKey="Breitinger, Silvia" sort="Breitinger, Silvia" uniqKey="Breitinger S" first="Silvia" last="Breitinger">Silvia Breitinger</name></region><name sortKey="Breitinger, Silvia" sort="Breitinger, Silvia" uniqKey="Breitinger S" first="Silvia" last="Breitinger">Silvia Breitinger</name></country><country name="France"><region name="Grand Est"><name sortKey="Lock, Hendrik C R" sort="Lock, Hendrik C R" uniqKey="Lock H" first="Hendrik C. R." last="Lock">Hendrik C. R. Lock</name></region><name sortKey="Lock, Hendrik C R" sort="Lock, Hendrik C R" uniqKey="Lock H" first="Hendrik C. R." last="Lock">Hendrik C. R. Lock</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 00CD18 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 00CD18 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:2FD619EC268C08B11C68A39EDE07A7ACA7E3F46F
|texte= Improving search for job-shop scheduling with CLP(FD)
}}
| This area was generated with Dilib version V0.6.33. |  |